package com.cwj.algorithm.linear;

/**
 * @author chenwujie
 * @date 2020/11/1610:42
 */
public class TwoPointers {
    /**
     * 给定一个单向链表，返回它的中间节点的值
     * @param head
     * @param <E>
     * @return
     */
    public static <E>  E getMind(Node<E> head){
        Node<E> slow = head;
        Node<E> fast = head;
        while (slow.next !=null && fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow.item;
    }

    /**
     * 快慢指针判断有环链表
     * @param head
     * @param <E>
     * @return
     */
    public static <E> boolean isCircle(Node<E> head){
        Node<E> slow = head;
        Node<E> fast = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)){
                return true;
            }
        }
        return false;
    }

    /**
     * 给定一个链表，求环入口节点
     * @param head
     * @param <E>
     * @return
     */
    public static <E> Node<E> getEntrance(Node<E> head){
        Node<E> slow = head;
        Node<E> fast = head;

        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow.equals(fast)){
                // 判断有环后，设置一个临时指针，当该指针与慢指针相遇时，则该指针指向的节点就是要找的环入口节点。
                Node<E> temp = head;
                while (!temp.equals(slow)){
                    temp = temp.next;
                    slow = slow.next;
                    fast = fast.next.next;
                }
                return temp;
            }
        }
        return null;
    }
}
